package pro.softzhang.algo.lc300;

import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.stream.Collectors;

public class LC373_FindKPairsWithSmallestSums {
    public static void main(String[] args) {

    }

    /**
     * 又是针对堆的题目
     */
    static class Solution {
        public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
            Queue<int[]> heap = new PriorityQueue<>((e1, e2) -> e2[0] + e2[1] - e1[0] - e1[1]);
            for (int i = 0; i < Math.min(k, nums1.length); i++) {
                for (int j = 0; j < Math.min(k, nums2.length); j++) {
                    if(heap.size() >= k) {
                        int[] root = heap.peek();
                        if(root[0] + root[1] > nums1[i] + nums2[j]) {
                            heap.poll();
                            heap.offer(new int[]{nums1[i], nums2[j]});
                        }
                    } else {
                        heap.offer(new int[]{nums1[i], nums2[j]});
                    }
                }
            }
            return heap.stream().map(arr -> Arrays.asList(arr[0], arr[1])).collect(Collectors.toList());
        }
    }
}